
import java.io.FileInputStream;
import java.io.IOException;

/**
 * 基于粒群算法求解数独游戏
 */
public class SudokuSolver {

    /**数独题目的文件位置，文件必须含有81个数字，需要填的空单元为数字0*/
    private static String topicfile = "C:\\Users\\Administrator\\Desktop\\IdeaProjects\\sudoku_solver\\src\\topic.txt";
    /**数独题目*/
    private static byte[][] topic;//前为行，后为列

    /**节点的数据结构*/
    public static class NodeStructure{
        /**当前节点的状态，即数独矩阵各个单元是否有唯一解，类似提示数*/
        public byte[][] status;
        /**当前节点的可能解，*/
        public byte[][][] possibleSolution;
        /**根据估价函数得到，从当前节点到下一节点的动作，即行列(action[0],action[1])的位置，填数字action[2]*/
        public byte[] action;
        /* 注意：此节点的possibleSolution变量中还留有action的数字，
         * 在解的过程中，子节点返回到此节点时，把possibleSolution里的action数字删除再做解
         * （即action里的数字解不出结果，则把此数字删除）
         */
        /**根据基本解决算法得到的，在基本解决算法中确定的唯一解存放在这，
         * actionList[0][0]存放当前列表的长度，actionList[x][0]存放行，
         * actionList[x][0]存放列，actionList[x][0]存放数字
         */
        public byte[][] actionList;
        /**父节点*/
        public NodeStructure fatherNode;
        /**深度*/
        public int depth;
        /**估价函数估的值*/
        public int value;

        /**构造函数*/
        public NodeStructure() {
            status = new byte[9][9];
            possibleSolution = new byte[9][9][10];
            action = new byte[3];
            actionList = new byte[82][3];
            fatherNode = null;
            depth=0;
            value=-1;
        }

        public void printfNode() {
            System.out.println("-----------节点信息如下-----------");
            System.out.println("深度值："+depth);
            System.out.println("提示数矩阵：");
            printfTopic(status);
            System.out.println("可能解矩阵：");
            printfAllPossibleSolution(possibleSolution);
            System.out.println("基本解决算法得到的唯一解：");
            for (int i=1;i<=actionList[0][0];i++){
                System.out.println("(R"+(actionList[i][0]+1)+",C"+(actionList[i][1]+1)+") 填入数字 "+actionList[i][2]);
            }
            System.out.println("估价函数得到的，向下一个节点的动作：(R"+(action[0]+1)+",C"+(action[1]+1)+") 填入数字 "+action[2]);
            System.out.println("估价函数的值："+value);
            System.out.println("---------------------------------");
        }
    }

    /**路径*/
    private static NodeStructure lastNode = null;

    /**记录到达的树深度*/
    private static int treeDepth;

    /**
     * 世界的入口，一切的起点
     */
    public static void main(String[] args){
        topic = new byte[9][9];

        try {
            setTopic('t');
        } catch (IOException io){
            System.out.println("异常：");
            io.printStackTrace();
        }

        printfTopic(topic);

        long beginTime = System.currentTimeMillis();
        int ret = AStarAlgorithm(topic);
        System.out.println("A*算法结果："+ret);
        long endTime = System.currentTimeMillis();
        System.out.println("time consumed:"+(endTime-beginTime)+"ms");
        if (ret>=0) {
//            printfAllPossibleSolution(lastNode.possibleSolution);
            System.out.println("验证："+validationFunction(lastNode.possibleSolution));
            System.out.println("最大树深："+treeDepth);
            System.out.println("当前树深："+lastNode.depth);
        }
//        System.out.println("++++++++++++++++++++++++++++++++++++++++++++++++");
//        printfAllNode(lastNode);
        System.out.println("++++++++++++++++++++++++++++++++++++++++++++++++");
        printfStepInSequence(lastNode,lastNode.depth);

//        byte[][][] possibleSolution = new byte[9][9][10];
//        long beginTime = System.currentTimeMillis();
//        System.out.println("结果："+basicSolution(topic,possibleSolution));
//        long endTime = System.currentTimeMillis();
//        System.out.println("time consumed:"+(endTime-beginTime)+"ms");
//        printfAllPossibleSolution(possibleSolution);


    }

    /**
     * 将文件中的数独题目读取出来，并放入变量topic中
     * 此方法会在文件中寻找num字符，并获取num字符后面81个数字，
     * 期间非数字符号会被忽略，直到获取满81个数字，
     * 并依次放入topic中
     */
    public static void setTopic(char num) throws IOException {
        FileInputStream topicFile = new FileInputStream(topicfile);
        byte[] temp = new byte[1024];
        int len,position=-1;

        while (true){         //搜索字符所在位置
            len = topicFile.read(temp,0,1024);
            for (int i=0;i<len;i++){
                if (temp[i]==num){
                    position = i;
                    break;
                }
            }
            if (position>=0)
                break;
        }
//        System.out.println(Arrays.toString(temp));
        for (int i=position,j=0,k=0;true;i++){
            if (i==len){
                len = topicFile.read(temp,0,1024);
                i = 0;
            }
//            System.out.println("i:"+i);
            if (temp[i]<=57 && temp[i]>=48){
                topic[j][k] = (byte) (temp[i]-48);//j为行，k为列
                k++;
                if (k>=9){
                    k=0;
                    if (++j>=9)
                        break;
                }
            }
        }
        topicFile.close();
    }

    /**
     * A*算法，返回小于-1为此数独无解，-2为超时，为正值为循环的次数
     */
    public static int AStarAlgorithm(byte[][] topic){
        byte[][] currentStatus = new byte[9][9];
        copyByte2D(topic,currentStatus);

//        boolean newNode = true;
        boolean revaluation = true;
        for (int ai=1;ai<=100000;ai++){
//            System.out.println("begin ai:"+ai);

            byte[][][] possibleSolution = new byte[9][9][10];
            int retB = basicSolution(currentStatus, possibleSolution);
//            if (newNode) {
                NodeStructure tempNode = new NodeStructure();//创建新节点
                copyByte2D(currentStatus,tempNode.status);
                copyByte3D(possibleSolution,tempNode.possibleSolution);
                tempNode.fatherNode = lastNode;
                if (lastNode == null) {
                    tempNode.depth = 1;
                    treeDepth = tempNode.depth;
                }
                else {
                    tempNode.depth = lastNode.depth + 1;
                    if (tempNode.depth>treeDepth)
                        treeDepth = tempNode.depth;
                }
                lastNode = tempNode;
//            } else {
//                copyByte3D(possibleSolution,lastNode.possibleSolution);
//            }
//            newNode = true;
            revaluation = true;

//            System.out.println("节点深度：" + lastNode.depth);
//            printfTopic(lastNode.status);
//            printfAllPossibleSolution(lastNode.possibleSolution);
//            printfPossibleSolution(possibleSolution);

            switch (retB) {
                case -1: {//超时
                    System.out.println("超时！（我赌一包辣条，这句不会被打印）");
                    if (lastNode == null) {
                        System.out.println("此数独无解");
                        return -1;
                    }
                }
                break;
                case 0: {//无解
//                    System.out.println("无解！");
                    while (true) {
                        lastNode = lastNode.fatherNode;
                        if (lastNode == null) {
                            System.out.println("此数独无解！");
                            return -1;
                        } else {//在possibleSolution中删除对应的action数字
//                            System.out.println("回调节点，深度："+lastNode.depth);
                            int ret = deleteAction(lastNode);
                            if (ret==0) {//删除action后此位置有不唯一的解，则跳出循环，进行估价
                                break;
                            } else if (ret==1){//删除action后此位置有唯一解，则跳出循环，且跳到下一节点
                                revaluation = false;
                                break;
                            }//若没有可能解，则回调到父节点
                        }
                    }
                }
                break;
                case 1: {//待解决
//                    System.out.println("继续解决！！");
                }
                break;
                case 2: {//已解决
                    recordActionLost(lastNode);
                    return ai;
                }
            }

            while (revaluation) {
                revaluation = false;
//                int returnValuation = valuationFunction(lastNode);//使用改进前算法
                int returnValuation2 = valuationFunction2(lastNode);//使用改进后算法
//                if (returnValuation < 0 || returnValuation > 90) {//使用改进前算法//返回父节点，并在possibleSolution中删除对应的action数字
                if (returnValuation2 < 0 || returnValuation2 > 738) {//使用改进后算法//返回父节点，并在possibleSolution中删除对应的action数字
//                    System.out.println("估价函数出错！" + returnValuation);
                    while (true) {
                        lastNode = lastNode.fatherNode;
                        if (lastNode == null) {
                            System.out.println("此数独无解！！");
                            return -1;
                        } else {//在possibleSolution中删除对应的action数字
                            int tret = deleteAction(lastNode);
//                            System.out.println("回调节点，深度："+lastNode.depth);
                            if (tret==0) {//删除action后此位置有不唯一的解，则跳出循环，且重新估价
                                revaluation = true;
                                break;
                            } else if (tret==1){//删除action后此位置有唯一解，则跳出循环，且跳到下一节点
                                break;
                            }//否则跳到父节点
                        }
                    }
                } else
                    lastNode.value = returnValuation2;//使用改进前算法，用returnValuation，使用改进后算法，用returnValuation2
            }
//            copyByte2D(lastNode.status,currentStatus);
            readPossibleSolution(lastNode.possibleSolution,currentStatus);
            currentStatus[lastNode.action[0]][lastNode.action[1]] = lastNode.action[2];
            recordActionLost(lastNode);


//            lastNode.printfNode();
//            System.out.println("end ai:"+ai);
//            System.out.println("depth:"+lastNode.depth);
//            System.out.println("action:"+(lastNode.action[0]+1)+" "+(lastNode.action[1]+1)+" "+lastNode.action[2]);
//            System.out.println();
        }
        return -2;
    }

    /**
     * 估价函数，f(n)=g(n)+h(n)
     * 函数g：每个单元中的每个数字的g为此单元可能解的个数，
     * 比如(1,2)位置的可能解有{3,6}，则3的g值为2，6的g值为2
     * 函数h：把可能解放入对应的单元，然后进行基本求解算法（即执行basicSolution函数），
     * 取没有唯一解的单元的数量作为此数的h，比如(1,2)位置的可能解为{3,6}，取3放入(1,2)
     * 位置，执行基本求解算法，统计求解后没有唯一解单元的数量做为3的h值（若求解过程，
     * 出现无解现象，则删除(1,2)位置的数字3）
     * 此方法为求出某个节点中估值最低的位置的可能解
     * 返回值为估值，范围在[0,90]，为-1或大于90则出错
     */
    public static int valuationFunction(NodeStructure node){
        int gValuation,hValuation=100;
        /*函数g*/
        int gMinimumQuantity = 10;
        /*用于记录可能解数量最少的不唯一解单元的位置，gRecord[x][0]记录行，gRecord[x][1]记录列*/
        byte[][] gRecord = new byte[81][2];
        int recordNum = 0;/*记录gRecord中已经记录位置的数量*/
        for (int i=0;i<9;i++){
            for (int j=0;j<9;j++){//i为行，j为列
                if (node.possibleSolution[i][j][0]>1){
                    if (node.possibleSolution[i][j][0]<gMinimumQuantity){
                        recordNum=0;
                        gMinimumQuantity = node.possibleSolution[i][j][0];
                        gRecord[recordNum][0] =(byte) i;
                        gRecord[recordNum][1] =(byte) j;
                        recordNum++;
                    } else if (node.possibleSolution[i][j][0]==gMinimumQuantity){
                        gRecord[recordNum][0] =(byte) i;
                        gRecord[recordNum][1] =(byte) j;
                        recordNum++;
                    }
                }
            }
        }
        gValuation = gMinimumQuantity;

//        printfPossibleSolution(node.possibleSolution);
//        System.out.println("recordNum:"+recordNum);
//        System.out.println("gMinimumQuantity:"+gMinimumQuantity);

//        int random =(int) System.currentTimeMillis() % allNum;
        /*函数h*/
        byte[][] tempStatus = new byte[9][9];
        for (int i=0;i<recordNum;i++){
            for (int j=0;j<gMinimumQuantity;j++){
                int row = gRecord[i][0];
                int column = gRecord[i][1];
//                copyByte2D(node.status,tempStatus);
                readPossibleSolution(node.possibleSolution,tempStatus);
                tempStatus[row][column] = node.possibleSolution[row][column][j+1];//把可能解放入提示数矩阵中
                byte[][][] tempPossibleSolution = new byte[9][9][10];
                int ret = basicSolution(tempStatus,tempPossibleSolution);

                int emptyCells;
                if (ret == 2){//问题已解决
                    emptyCells = 0;
                } else if (ret == 1){//问题待解决
                    emptyCells = 0;
                    for (int ti=0;ti<9;ti++){
                        for (int tj=0;tj<9;tj++){
                            if (tempPossibleSolution[ti][tj][0]>1){
                                emptyCells++;
                            }
                        }
                    }
                } else{//出错，将此位置的此数删除
                    emptyCells = 100;

//                    System.out.println(ret+":11delete number:"+(row+1)+" "+(column+1)+" "+tempStatus[row][column]);

                    node.possibleSolution[row][column][0]--;
                    if (node.possibleSolution[row][column][0]==0)
                        return -1;//如果此单元没有待选数字，说明已经无法在解
                    for (int ti=j+1;ti<=node.possibleSolution[row][column][0];ti++){
                        node.possibleSolution[row][column][ti]=node.possibleSolution[row][column][ti+1];
                    }
                }
//                System.out.println("emptyCells:"+emptyCells);
                if (emptyCells < hValuation){
                    hValuation = emptyCells;
                    node.action[0] =(byte) row;
                    node.action[1] =(byte) column;
                    node.action[2] = tempStatus[row][column];
                }
                if (hValuation == 0)
                    break;
            }
            if (hValuation == 0)
                break;
        }
        return gValuation + hValuation;
    }

    /**
     * 估价函数，f(n)=g(n)+h(n)
     * 函数g：每个单元中的每个数字的g为此单元可能解的个数，
     * 比如(1,2)位置的可能解有{3,6}，则3的g值为2，6的g值为2
     * 函数h：把可能解放入对应的单元，然后进行基本求解算法（即执行basicSolution函数），
     * 取所有单元的所有可能解的数量做为此数的h，比如(1,2)位置的可能解为{3,6}，取3放入(1,2)
     * 位置，执行基本求解算法，统计求解后所有单元的所有可能解的数量做为3的h值（若求解过程，
     * 出现无解现象，则删除(1,2)位置的数字3）
     * 此方法为求出某个节点中估值最低的位置的可能解
     * 返回值为估值，范围在[0,738]，为-1或大于738则出错
     */
    public static int valuationFunction2(NodeStructure node){
        int gValuation,hValuation=730;
        /*函数g*/
        int gMinimumQuantity = 10;
        /*用于记录可能解数量最少的不唯一解单元的位置，gRecord[x][0]记录行，gRecord[x][1]记录列*/
        byte[][] gRecord = new byte[81][2];
        int recordNum = 0;/*记录gRecord中已经记录位置的数量*/
        for (int i=0;i<9;i++){
            for (int j=0;j<9;j++){//i为行，j为列
                if (node.possibleSolution[i][j][0]>1){
                    if (node.possibleSolution[i][j][0]<gMinimumQuantity){
                        recordNum=0;
                        gMinimumQuantity = node.possibleSolution[i][j][0];
                        gRecord[recordNum][0] =(byte) i;
                        gRecord[recordNum][1] =(byte) j;
                        recordNum++;
                    } else if (node.possibleSolution[i][j][0]==gMinimumQuantity){
                        gRecord[recordNum][0] =(byte) i;
                        gRecord[recordNum][1] =(byte) j;
                        recordNum++;
                    }
                }
            }
        }
        gValuation = gMinimumQuantity;

//        printfPossibleSolution(node.possibleSolution);
//        System.out.println("recordNum:"+recordNum);
//        System.out.println("gMinimumQuantity:"+gMinimumQuantity);

//        int random =(int) System.currentTimeMillis() % allNum;
        /*函数h*/
        byte[][] tempStatus = new byte[9][9];
        for (int i=0;i<recordNum;i++){
            for (int j=0;j<gMinimumQuantity;j++){
                int row = gRecord[i][0];
                int column = gRecord[i][1];
//                copyByte2D(node.status,tempStatus);
                readPossibleSolution(node.possibleSolution,tempStatus);
                tempStatus[row][column] = node.possibleSolution[row][column][j+1];//把可能解放入提示数矩阵中
                byte[][][] tempPossibleSolution = new byte[9][9][10];
                int ret = basicSolution(tempStatus,tempPossibleSolution);

//                System.out.println("row+column+number:"+row+" "+column+" "+tempStatus[row][column]);
//                System.out.println("tempPossibleSolution return:"+ret);

                int possibleNum;
                if (ret == 2){//问题已解决
                    possibleNum = 81;
                } else if (ret == 1){//问题待解决
                    possibleNum = 0;
                    for (int ti=0;ti<9;ti++){
                        for (int tj=0;tj<9;tj++){
                            possibleNum += tempPossibleSolution[ti][tj][0];
                        }
                    }
                } else{//出错，将此位置的此数删除
                    possibleNum = 730;
//                    System.out.println(ret+":11delete number:"+(row+1)+" "+(column+1)+" "+tempStatus[row][column]);
                    node.possibleSolution[row][column][0]--;
                    if (node.possibleSolution[row][column][0]==0)
                        return -1;//如果此单元没有待选数字，说明已经无法在解
                    for (int ti=j+1;ti<=node.possibleSolution[row][column][0];ti++){
                        node.possibleSolution[row][column][ti]=node.possibleSolution[row][column][ti+1];
                    }
                }
//                System.out.println("emptyCells:"+emptyCells);
                if (possibleNum < hValuation){
                    hValuation = possibleNum;
                    node.action[0] =(byte) row;
                    node.action[1] =(byte) column;
                    node.action[2] = tempStatus[row][column];
                }
                if (hValuation == 0)
                    break;
            }
            if (hValuation == 0)
                break;
        }
        return gValuation + hValuation;
    }

    /**
     * 删除节点中possibleSolution变量中，对应的action数字
     * 删除之后，还要进行估价，
     * 如果此单元没有待选数字，说明已经无法在解
     * 返回-1表示出错，0表示成功且剩下的可能解有多个，1表示成功且剩下的可能解唯一
     */
    public static int deleteAction(NodeStructure node){
        byte row = node.action[0];//行
        byte column = node.action[1];//列
        byte number = node.action[2];//数字

//        System.out.println("22delete number:"+(row+1)+" "+(column+1)+" "+number);

        node.possibleSolution[row][column][0]--;
        if (node.possibleSolution[row][column][0]==0)
            return -1;//如果此单元没有待选数字，说明已经无法在解
        for (int i=1;i<10;i++){
            if (node.possibleSolution[row][column][i]==number){
                for (int ti=i;ti<=node.possibleSolution[row][column][0];ti++){
                    node.possibleSolution[row][column][ti]=node.possibleSolution[row][column][ti+1];
                }
                break;
            }
        }
        if (node.possibleSolution[row][column][0]==1) {
//            node.status[row][column] = node.possibleSolution[row][column][1];//添加唯一值到提示数矩阵
            node.action[2] = node.possibleSolution[row][column][1];
            return 1;
        }
        return 0;
    }

    /**
     * 记录actionList
     */
    public static void recordActionLost(NodeStructure node){
        node.actionList[0][0] = 0;
        for (int i=0;i<9;i++){
            for (int j=0;j<9;j++){
                if (!(i==node.action[0]&&j==node.action[1]))//action位置不用记录
                    if (node.status[i][j]==0 && node.possibleSolution[i][j][0]==1) {
                        byte temp = (byte) (node.actionList[0][0]+1);
                        node.actionList[0][0] = temp;
                        node.actionList[temp][0] = (byte) i;
                        node.actionList[temp][1] = (byte) j;
                        node.actionList[temp][2] = node.possibleSolution[i][j][1];
                    }
            }
        }
    }

    /**
     * 数独的基本解决方法：余数法。根据已经有的提示数，确定每个空单元的数字，
     * 直到某个单元无数可填（即解失败，此时返回0）
     * 或数独用屏弃法已经无法确定的时候（此时返回1）
     * 或数独已经解决的时候（此时返回2）
     * 若超时返回-1
     * 参数：topic为提示数矩阵（此方法不更改其值），
     * possibleSolution为可能解矩阵（其做为可返回的参数）
     */
    public static int basicSolution(byte[][] topic,byte[][][] possibleSolution){
        byte[][][] tempPossibleSolution;
        byte[][] currentStatus = new byte[9][9];//用于记录当前题目状态
        byte[][] lastStatus = new byte[9][9];//用于记录上次题目状态
        copyByte2D(topic,currentStatus);
        for (int i=1;i<=100;i++){
//            System.out.println("time:"+i);
            tempPossibleSolution = new byte[9][9][10];
            int ret = getPossibleSolutionsForEmptyCells(currentStatus,tempPossibleSolution);

//            printfTopic(currentStatus);
//            printfAllPossibleSolution(tempPossibleSolution);

            if (ret==0){
//                System.out.println("出错！");
                return 0;
            } else if (ret==1){
                copyByte2D(currentStatus,lastStatus);
                readPossibleSolution(tempPossibleSolution,currentStatus);
                if (comparedByte2D(lastStatus,currentStatus)) {
//                    System.out.print("同:");
                    copyByte3D(tempPossibleSolution,possibleSolution);
                    return 1;
                }
//                else {
//                    System.out.print("不:");
//                }
            } else if (ret==2){
//                System.out.println("已经解决！");
                copyByte3D(tempPossibleSolution,possibleSolution);
                return 2;
            }
//            if (i>100){
//                System.out.println("超时！");
//                return -1;
//            }
        }
        System.out.println("超时！");
        return -1;
    }

    /**
     * 获取所有空单元的可能解，返回为0为无解，1为已搜索完所有的可能解，2为此题目已解决
     * topic为要寻找可能解的数独矩阵，前位行，后为列
     * possibleSolution（做为返回的参数）为空单元的可能解，前为行，中为列，后为可能解
     * （possibleSolution[x][x][0]放置的数值是(x,y)位置的可能解得数量
     * 若无可能解则possibleSolution[x][x][0]置0，
     * 若此单元有可能解，则将可能解得数量放入possibleSolution[x][x][0]中，
     * 并将可能解由小到大放入possibleSolution[x][x][1]至possibleSolution[x][x][9]中，
     * 其他情况的值置0）
     */
    public static int getPossibleSolutionsForEmptyCells(byte[][] topic,byte[][][] possibleSolution){
        int uniqueSolution=0;//记录此题目中单元的唯一解的个数，若唯一解为81个，则此题目已解决
        for (int i=0;i<9;i++){//将提示数做为唯一解放入possibleSolution中
            for (int j=0;j<9;j++){
                if (topic[i][j]>0){
                    possibleSolution[i][j][0] = 1;
                    possibleSolution[i][j][1] = topic[i][j];
                    uniqueSolution++;
                }
            }
        }

//        System.out.println("getPossibleSolutionsForEmptyCells begin:");
//        printfAllPossibleSolution(possibleSolution);

        for (int row=0;row<9;row++){
            for (int column=0;column<9;column++){
                if (possibleSolution[row][column][0]==0){//若此单元可能解数量为空，则搜索可能解
                    byte[] temp = {9,1,2,3,4,5,6,7,8,9};
                    for (int ti=0;ti<9;ti++){//搜索这行数字，将出现的数字去掉
                        if (possibleSolution[row][ti][0]==1){
                            for (int tj=1;tj<10;tj++)//将temp中的对应数字置0
                                if (temp[tj]==possibleSolution[row][ti][1]){
                                    temp[tj]=0;
                                    temp[0]--;
                                    break;
                                }
                        }
                    }
                    for (int ti=0;ti<9;ti++){//搜索这列数字，将出现的数字去掉
                        if (possibleSolution[ti][column][0]==1){
                            for (int tj=1;tj<10;tj++)//将temp中的对应数字置0
                                if (temp[tj]==possibleSolution[ti][column][1]){
                                    temp[tj]=0;
                                    temp[0]--;
                                    break;
                                }

                        }
                    }
                    int grow=row/3,gcolumn=column/3;
                    for (int ti=0;ti<3;ti++){//搜索这宫数字，将出现的数字去掉
                        for (int tj=0;tj<3;tj++){
                            if (possibleSolution[grow*3+ti][gcolumn*3+tj][0]==1){
                                for (int tk=1;tk<10;tk++)//将temp中的对应数字置0
                                    if (temp[tk]==possibleSolution[grow*3+ti][gcolumn*3+tj][1]){
                                        temp[tk]=0;
                                        temp[0]--;
                                        break;
                                    }
                            }
                        }
                    }
                    //排除了所有的不可能的解，获得此空单元的可能解
                    if (temp[0]<=0){//若此处无解，则后面就不用算了
                        return 0;
                    } else if (temp[0]==1){
                        uniqueSolution++;
                    }
                    possibleSolution[row][column][0] = temp[0];
                    for (int ti=1,tj=1;ti<10;ti++){//若temp[0]大于0，则表示此处有可能解
                        if (temp[ti]>0){
                            possibleSolution[row][column][tj] = temp[ti];
                            tj++;
                        }
                    }
//                    if (temp[0]==1)
//                        System.out.println("add:row+column+number:"+(i+1)+" "+(j+1)+" "+possibleSolution[i][j][1]);

                }
            }
        }

//        System.out.println("getPossibleSolutionsForEmptyCells end:");
//        printfAllPossibleSolution(possibleSolution);

        if (uniqueSolution==81)
            return 2;
        else
            return 1;
    }

    /**
     * 在可能解矩阵possibleSolution中，搜索每个单元，
     * 若此单元有唯一解，则将此唯一解放入target中对应位置
     */
    public static void readPossibleSolution(byte[][][] possibleSolution,byte[][] target){
        for (int i=0;i<9;i++){
            for (int j=0;j<9;j++){      //i为行，j为列,possibleSolution和target一致
                if (possibleSolution[i][j][0]==1){
                    target[i][j] = possibleSolution[i][j][1];
                } else if (possibleSolution[i][j][0]>1){
                    target[i][j] = 0;
                } else {
                    System.out.println("readPossibleSolution:error!");//小于1，说明此处无解
                    return;
                }
            }
        }
    }

    /**
     * 按照节点的先后顺序打印节点
     */
    public static void printfAllNode(NodeStructure node){
        if (node.fatherNode==null){
            node.printfNode();
        } else {
            printfAllNode(node.fatherNode);
            node.printfNode();
        }
    }

    /**
     * 按照步骤的先后顺序打印
     */
    public static void printfStepInSequence(NodeStructure node,int depth){
        if (depth ==1){
            for (int i=1;i<=node.actionList[0][0];i++){
                System.out.println("(R"+(node.actionList[i][0]+1)+",C"+(node.actionList[i][1]+1)+") 填入数字 "+node.actionList[i][2]);
            }
            System.out.println("(R"+(node.action[0]+1)+",C"+(node.action[1]+1)+") 填入数字 "+node.action[2]);
        } else {
            printfStepInSequence(node.fatherNode, depth - 1);
            for (int i=1;i<=node.actionList[0][0];i++){
                System.out.println("(R"+(node.actionList[i][0]+1)+",C"+(node.actionList[i][1]+1)+") 填入数字 "+node.actionList[i][2]);
            }
            if (depth!=lastNode.depth)
                System.out.println("(R"+(node.action[0]+1)+",C"+(node.action[1]+1)+") 填入数字 "+node.action[2]);
        }
    }


    /**
     * 复制二维byte
     */
    public static void copyByte2D(byte[][] origin,byte[][] target){
        for (int i=0;i<9;i++){
            System.arraycopy(origin[i], 0, target[i], 0, 9);
        }
    }

    /**
     * 比较两个二维byte，返回true为两个相同，false为不同
     */
    public static boolean comparedByte2D(byte[][] arg1,byte[][] arg2){
        for (int i=0;i<9;i++){
            for (int j=0;j<9;j++){
                if (arg1[i][j]!=arg2[i][j]){
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 复制三维byte
     */
    public static void copyByte3D(byte[][][] origin,byte[][][] target){
        for (int i=0;i<9;i++){
            for (int j=0;j<9;j++){
                for (int k=0;k<10;k++){
                    target[i][j][k] = origin[i][j][k];
                }
            }
        }
    }

    /**
     * 以九宫格的方式打印topic
     */
    public static void printfTopic(byte[][] topic){
        System.out.println("topic:");
        for (int ti=0;ti<9;ti++){//i为行，j为列
            for (int tj=0;tj<9;tj++){
                System.out.print(topic[ti][tj]+" ");
            }
            System.out.println("");
        }
    }

    /**
     * 以九宫格的方式打印possibleSolution的每个单元可能解数量
     */
    public static void printfPossibleSolution(byte[][][] possibleSolution){
        System.out.println("possibleSolution:");
        for (int ti=0;ti<9;ti++){//i为行，j为列
            for (int tj=0;tj<9;tj++){
                System.out.print(possibleSolution[ti][tj][0]+" ");
            }
            System.out.println("");
        }
    }

    /**
     * 以九宫格的方式打印possibleSolution的每个单元的全部可能解
     */
    public static void printfAllPossibleSolution(byte[][][] possibleSolution){
        System.out.println("all possibleSolution:");
        for (int ti=0;ti<9;ti++){//i为行，j为列
            for (int tj=0;tj<9;tj++){
                if (possibleSolution[ti][tj][0]==0)
                    System.out.print(possibleSolution[ti][tj][0]+"  ");
                else
                    for (int tk=1;tk<=possibleSolution[ti][tj][0];tk++)
                        if (tk==possibleSolution[ti][tj][0])
                            System.out.print(possibleSolution[ti][tj][tk]+"  ");
                        else
                            System.out.print(possibleSolution[ti][tj][tk]);
            }
            System.out.println("");
        }
    }

    /**
     * 验证possibleSolution中每个单元的可能解是否唯一，且全部解是否符合数独游戏规则
     */
    public static boolean validationFunction(byte[][][] possibleSolution){
        boolean ret = true;
        for (int row=0;row<9;row++){
            for (int column=0;column<9;column++){
                if (possibleSolution[row][column][0]!=1){
                    System.out.println("行+列+可能解数量：" + row + " " + column + " " + possibleSolution[row][column][0]);
                    ret = false;
//                    return false;
                }
                else {
                    for (int ti=0;ti<9;ti++){//搜索这行数字
                        if (column!=ti)
                            if (possibleSolution[row][column][1]==possibleSolution[row][ti][1]){
                                System.out.println("行:列+行:列+数字：" + row + ":" + column + " " + row + ":" + ti + " " + possibleSolution[row][column][1]);
                                ret = false;
//                                return false;
                            }
                    }
                    for (int ti=0;ti<9;ti++){//搜索这列数字
                        if (row!=ti)
                            if (possibleSolution[row][column][1]==possibleSolution[ti][column][1]){
                                System.out.println("行:列+行:列+数字：" + row + ":" + column + " " + row + ":" + ti + " " + possibleSolution[row][column][1]);
                                ret = false;
//                                return false;
                            }
                    }
                    int grow=row/3,gcolumn=column/3;
                    for (int ti=0;ti<3;ti++){//搜索这宫数字，将出现的数字去掉
                        for (int tj=0;tj<3;tj++){
                            if (row!=(grow*3+ti) && column!=(gcolumn*3+tj))
                                if (possibleSolution[grow*3+ti][gcolumn*3+tj][1]==possibleSolution[row][column][1]){
                                    System.out.println("行:列+行:列+数字：" + row + ":" + column + " " + row + ":" + ti + " " + possibleSolution[row][column][1]);
                                    ret = false;
//                                return false;
                                }
                        }
                    }
                }
            }
        }
        return ret;
    }
}
